import java.util.Scanner;

public class fib {
    public static void main(String[] args) {
        long[] f=new long[100001];
        f[0]=1;f[1]=1;
        for (int i = 2; i < 100001; i++) {
            long num=f[i-1]+f[i-2];
            f[i]=num%1000000;
        }
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n= sc.nextInt();
            System.out.println(f[n]);
        }
    }
}
